package Leetcode.树;


import java.util.ArrayList;
import java.util.List;

/**
 * @Author: kirito
 * @Date: 2024/9/28 16:03
 * @Description:
 */

class 完全二叉树插入器 {
    // 使用ArrayList来存储完全二叉树的所有节点，保持层级遍历的顺序
    List<TreeNode> list = new ArrayList<>();
    // idx用于追踪下一个需要插入子节点的父节点位置
    int idx = 0;

    // 构造函数，初始化完全二叉树插入器
    public 完全二叉树插入器(TreeNode root) {
        // 将根节点添加到列表中
        list.add(root);
        // 当前节点索引
        int cur = 0;
        // 层次遍历树，将所有节点添加到列表中
        while (cur < list.size()) {
            TreeNode node = list.get(cur);
            // 如果左子节点存在，添加到列表中
            if (node.left != null) {
                list.add(node.left);
            }
            // 如果右子节点存在，添加到列表中
            if (node.right != null) {
                list.add(node.right);
            }
            // 移动到下一个节点
            cur++;
        }
    }

    // 插入一个新值到完全二叉树中
    public int insert(int val) {
        // 创建新节点
        TreeNode node = new TreeNode(val);
        // 找到下一个应该插入子节点的父节点
        while (list.get(idx).left != null && list.get(idx).right != null) {
            idx++;
        }
        // 获取该父节点
        TreeNode fa = list.get(idx);
        // 如果左子节点为空，则将新节点作为左子节点
        if (fa.left == null) {
            fa.left = node;
        }
        // 否则，将新节点作为右子节点
        else if (fa.right == null) {
            fa.right = node;
        }
        // 将新节点添加到列表中
        list.add(node);
        // 返回父节点的值
        return fa.val;
    }

    // 获取完全二叉树的根节点
    public TreeNode get_root() {
        // 返回列表中的第一个元素，即根节点
        return list.get(0);
    }
}